import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/2 15:32
 * @description HashSet + 贪心 从左到右遍历
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {-1, 3, 5, 1, 4, 2, -9};
        solution.maxNonOverlapping(nums, 6);
    }
    public int maxNonOverlapping(int[] nums, int target) {
        int size = nums.length;
        int ret = 0;
        int i = 0, sum = 0;
        // 记录前 i个元素的和，需要提前加入 0
        Set<Integer> set = new HashSet<Integer>();
        set.add(0);
        while (i < size) {
            while (i < size) {
                // 以i结尾的前缀和为 sum，如果前面出现了 sum - target, 假设为j位置，那么 j - i这部分的和为 sum - (sum - target) = target，
                sum += nums[i];
                if (set.contains(sum - target)) {
                    ret++;
                    sum = 0;
                    set.clear();
                    break;
                } else {
                    set.add(sum);
                    i++;
                }
            }
            i++;
        }
        return ret;
    }
}
